package reviewAlgorithms.dynamicProgramming;

public class FindMaxForm {
    public static void main(String[] args) {
        String[] strs = {"10","001","111001","1","0"};
        int m = 5;
        int n = 3;
        System.out.println(findMaxForm(strs,m,n));
    }
    public static int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length < 1){
            return 0;
        }
        int[][][] dp = new int[strs.length][m + 1][n + 1];
        int[] temp = getMN(strs[0]);
        for (int i = 0; i < m + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                if (temp[0] <= i && temp[1] <= j){
                    dp[0][i][j] = 1;
                }
            }
        }
        for (int i = 1; i < strs.length; i++) {
            temp = getMN(strs[i]);
            for (int j = 0; j < m + 1; j++) {
                for (int k = 0; k < n + 1; k++) {
                    if (temp[0] > j || temp[1] > k){
                        dp[i][j][k] = dp[i - 1][j][k];
                    }else {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k],dp[i - 1][j - temp[0]][k - temp[1]] + 1) ;
                    }
                }
            }
        }
        return dp[strs.length - 1][m][n];
    }

    private static int[] getMN(String str) {
        int[] mn = new int[2];
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0'){
                mn[0] += 1;
            }else {
                mn[1] += 1;
            }
        }
        return mn;
    }

}
